package Calculation;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-10-06
 * Time: 11:44
 */
class Solution {
    //有效三角形个数
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        int count = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = i+1 ; j < n ; j++){
                for(int k = j+1 ; k < n ; k++){
                    int result =  search(nums[i],nums[j],nums[k]);
                    if (result == 1){
                        count++;
                    }
                }
            }
        }
        return count;
    }
    public int search(int i , int j , int k){
        int sum = i+j+k;
        int max = Math.max(i,Math.max(j,k));
        int min = Math.min(i,Math.max(j,k));
        int mid = sum-max-min;
        int tem = min + mid;
        if(tem > max){
            return 1;
        }else{
            return 0;
        }
    }
}

class Solution2{
    //优化解法
    class Solution {
        public int triangleNumber(int[] nums) {
            int end = nums.length-1;
            Arrays.sort(nums);
            int count = 0;
            for( ; end >= 0 ; end--){
                int right = end-1;
                int left = 0;
                while(left < right){
                    int tem = nums[left] + nums[right];
                    if(tem > nums[end]){
                        count += right - left;
                        right--;
                    }else{
                        left++;
                    }
                }
            }
            return count;
        }
    }
}
public class Test5 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2,2,3,4};
        int result = solution.triangleNumber(nums);
        System.out.println(result);
    }
}
